#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:

    // leetcode: 611. 有效三角形的个数
    // https://leetcode.cn/problems/valid-triangle-number/description/
    int triangleNumber(vector<int>& nums) {
        //  优化顺序
        sort(nums.begin(), nums.end());

        int c = nums.size()-1;
        int cnt = 0;
        while (c >= 2)
        {
            int b = c-1;
            int a = 0;
            while (a < b)
            {
                // 利用单调性的原理，若左边最小和右边最大的和大于c，那么右边最大与右边最小之间的数的和一定大于c
                if (nums[a] + nums[b] > nums[c])
                {
                    cnt += (b-a);
                    --b;
                }
                else 
                {
                    ++a;
                }
            }
            --c;
        }
        return cnt;
    }

    // leetcode: 剑指 Offer 57. 和为s的两个数字
    // https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/

    // 解法一：二分查找 
    // 时间复杂度：O(nlogn)
    // vector<int> twoSum(vector<int>& nums, int target) {
    //     vector<int> ans(2);
    //     for (auto& num : nums)
    //     {
    //         int other = target - num;
    //         if (binary_search(nums.begin(), nums.end(), other))
    //         {
    //             ans[0] = num;
    //             ans[1] = other;
    //             break;
    //         }
    //     }
    //     return ans;
    // }

    // 解法二：双指针
    // 时间复杂度：O(n)
    vector<int> twoSum(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while (left < right)
        {
            int sum = nums[left] + nums[right];
            if (sum > target)
            {
                --right;
            }
            else if (sum < target)
            {
                ++left;
            }
            else 
            {
                return { nums[left], nums[right] };
            }
        }

        return {-1, -1};
    }

    // leetcode : 15. 三数之和
    // https://leetcode.cn/problems/3sum/
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int a = 0;
        vector<vector<int>> ans;
        while (a < nums.size())
        {
            if (nums[a] > 0) break; // 排序之后找不到大于0的相反数
            int left = a + 1;
            int right = nums.size() - 1;
            int target = -nums[a];
            // 找两个数之和为target的数
            while (left < right)
            {
                int sum = nums[left] + nums[right];
                if (sum > target) 
                    --right;
                else if (sum < target)
                    ++left;
                else // == 
                {
                    ans.push_back({nums[a], nums[left], nums[right]});
                    // 跳过相同的数
                    do 
                    {
                        ++left;
                    }while (left<right && nums[left] == nums[left-1]);
                    do 
                    {
                        --right;
                    }while (left<right && nums[right] == nums[right+1]);
                }
            }
            // 跳过相同的数
            do 
            {
                ++a;
            }while (a < nums.size() && nums[a] == nums[a-1]);
        }
        return ans;
    }

    // leetcode : 18. 四数之和
    // https://leetcode.cn/problems/4sum/
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());

        vector<vector<int>> ans;
        for (int a = 0; a<nums.size(); )
        {
            long three_sum = target - nums[a];
            for (int b = a + 1; b < nums.size(); )
            {
                long tow_target = three_sum - nums[b];
                int c = b + 1;
                int d = nums.size() - 1;
                while (c < d)
                {
                    long tow_sum = nums[c] + nums[d];
                    if (tow_sum < tow_target) ++c;
                    else if (tow_sum > tow_target) --d;
                    else 
                    {
                        ans.push_back({nums[a], nums[b], nums[c], nums[d]});
                        do { ++c; }while (c < d && nums[c] == nums[c-1]);
                        do { --d; }while (c < d && nums[d] == nums[d+1]);
                    }
                }
                do { ++b; }while (b<nums.size() && nums[b] == nums[b-1]);
            }
            do { ++a; }while (a<nums.size() && nums[a] == nums[a-1]);
        }

        return ans;
    }
};